package immutablecollections;

import immutablecollections.exceptions.*;
import immutablecollections.functions.*;
import immutablecollections.misc.*;
import java.io.*;
import java.util.*;
/**
 * A functional style list (Java programmers
 * would probably think of it as a very unbalanced binary tree).
 * 
 * ## Introduction
 * 
 * <img src="doc-files/classes-focus-on-list.png" alt="classes-focus-on-list" style="width: 40em"/>
 * 
 * Like all the other collection classes in this library, `ImLists` are *immutable*. You *can't change* a list
 * once it has been created - you can only create new lists - although new lists will often share nodes
 * with old lists. In this respect, these collections are similar to the standard Java `String` class,
 * which is also immutable.
 * 
 * Each node in an `ImList<T>` is either:
 * 
 * * The Empty List
 * * A node containing `head` - a value of type `T` and `tail` - a reference to another `ImList<T>`
 * 
 * For example, this list of Strings:
 * 
 *     ["a", "b", "c"]
 * 
 * would look like this:
 * 
 * <img src="doc-files/list-head-tail.png" alt="list-head-tail" /></p>
 * 
 * As you can see, it doesn't look very much like a standard Java List.
 * 
 * `ImLists` are not intended to be random access collections. The nearest `Im` equivalent to the standard Java list
 * is {@link ImShelf}.
 * 
 * 
 * ## Standard ImCollection methods implemented by this class:
 * 
 * - {@link #onArray(Object...)}
 * - {@link #onAll(Collection)}
 * - {@link #onIterator(Iterator)}
 * - {@link #on(Object)}
 * - {@link #empty()}
 * - {@link #joinArray(Collection...)}
 * - {@link #joinIterator(Iterator)}
 * - {@link #join(Collection)}
 * - {@link #addingAll(Collection)}
 * - {@link #upCast()}
 * - {@link #contains(Object)}
 * - {@link #size()}
 * - {@link #iterator()}
 * - {@link #toString()}
 * - {@link #map(Function1)}
 * 
 * See the <a href="{@docRoot}/immutablecollections/package-summary.html">package summary</a>
 * for more details of the standard methods.
 * 

 * ## Basic Methods
 * 
 * The *fundamental* `ImList` methods are:
 * 
 * A static factory method to construct a new list out of another list by 'adding' a new element at the front:
 * 
 *     ImList<T> cons(T head, ImList<? extends T> tail)
 * 
 * Accessors for the head and tail:
 * 
 *     T head()
 *     ImList<T> tail()
 * 
 * All the other methods have been implemented in terms of these (but see below about recursion).
 * 
 * 
 * ## Accessing single elements
 * 
 * - {@link #get1(int)}
 * - {@link #get(int)}
 * - {@link #head()}
 * 
 * ## Accessing sub-lists
 * 
 * - {@link #drop}
 * - {@link #tail()}
 * - {@link #take}
 * 
 * ## Obtaining a new list by processing the current list
 * 
 * - {@link #reversed}
 * - {@link #intersperse}
 * - {@link #powerSet}
 * 
 * 
 * All functional flavoured Java libraries try to implement some *functions-as-first-class-objects* fu
 * and this is our offering in this area.
 * 
 * See the package {@link immutablecollections.functions} for more details.
 * 
 * 
 * ## No Deep Recursion
 * 
 * If you are familiar with functional lists from ML or Haskell, you might be wondering about the stack
 * usage since list functions in these languages are recursive.
 * 
 * We could have used recursion for many functions - and it would certainly have meant more elegant
 * and more compact code - but we made the design decision to avoid it. This means that large lists can be processed
 * **without** consuming large amounts of stack space.
 * 
 * In experimental versions of this class we *have* used recursion and found that it appears to
 * give reasonable performance on Java 64 bit VMs with a sufficiently large stack size. The recursive
 * approach only seemed to be significantly slower when manipulating lists with more than about a million objects.
 * 
 * ## The Empty List
 * 
 * The empty list is a singleton object. It is not possible to create another empty list.
 * 
 * It can be accessed using
 * 
 *     ImList.empty();
 *     
 * or
 * 
 *     ImList.on();
 *     
 * You can test for a list being empty by
 * 
 *     list.isEmpty();
 *     
 * or, since it is a singleton
 * 
 *     list == ImList.empty();
 * 
 * This is similar to what is done in the Java class {@link java.util.Collections#emptyList()} but with the
 * extra rule that the *only* empty list allowed is this singleton object.
 * 
 * ## Example
 * 
 * To create the list
 * 
 *     ["a", "b", "c"]
 * 
 *  you could do it the long way using {@link ImList#cons}:
 * 
 *     ImList<String> c = ImList.cons("c", ImList.<String> empty());
 *     ImList<String> b = ImList.cons("b", c);
 *     ImList<String> a = ImList.cons("a", b);
 * 
 * or you could use the factory method {@link ImList#on}:
 * 
 *     ImList<String> a = ImList.onArray("a", "b", "c");
 * 
 * @see ImShelf
 *
 */
public class ImList<T> extends ImCollection<T>
{
    final private T head;
    final private ImList<T> tail;
    final private int size;
    final private int hashCode;

    // The cons method, as a function
    final private static Function2<ImList<?>> consFn = //
    FnFactory.on(ImList.class).getFnStatic(ImList.class, "cons", Object.class, ImList.class);

    final private static ImList<?> empty = new ImList<Object>();

    ImList(T head, ImList<T> tail)
    {
        NullCheck.check(head);
        this.head = head;
        this.tail = tail;
        this.size = tail.size() + 1;
        hashCode = head.hashCode() + 31 * tail.hashCode();
    }

    private ImList()
    {
        this.head = null;
        this.tail = null;
        this.size = 0;
        this.hashCode = 1;
    }

    /**
     * The head element of the list.
     * 
     * ### Examples:
     * 
     *     ImList.on(1, 2, 3, 4).head()  =>  1
     *     ImList.on(7).head()           =>  7
     *     ImList.on().head()            =>  throws NoSuchElementException
     * 
     * @throws NoSuchElementException if invoked on the empty list
     */
    public T head()
    {
        if (isEmpty())
            throw new NoSuchElementException("You tried to use head() on an empty list");
        else
            return head;
    }

    /**
     * The tail of the list.
     * 
     * ### Examples:
     * 
     *     ImList.on(1, 2, 3, 4).tail()  =>  [2, 3, 4]
     *     ImList.on(7).tail()           =>  []
     *     ImList.on().tail()            =>  throws NoSuchElementException
     * 
     * @throws NoSuchElementException if invoked on the empty list
     */
    public ImList<T> tail()
    {
        if (isEmpty())
            throw new NoSuchElementException("You tried to use tail() on an empty list");
        else
            return tail;
    }

    /**
     * The number of elements in `this`.
     */
    @Override
    public int size()
    {
        return size;
    }

    /**
     * An iterator over the elements in `this` in proper sequence.
     *
     * Note that the iterator returned by this method will throw an
     * `UnsupportedOperationException` in response to its
     * `remove` method.
     *
     */
    @Override
    public Iterator<T> iterator()
    {
        return new ImListIterator<T>(this);
    }

    /**
     * The element at `indexStartingAtOne`.
     * 
     * Note that the index starts at *one* (as nature intended), not zero.
     * 
     * ### Examples:
     * 
     *     ImList.on(1, 2, 3, 4).at(2) =>  2
     *     ImList.on(7).at(1)          =>  7
     *     ImList.on().at(3)           =>  throws ImIndexOutOfBoundsException
     *     ImList.on().at(-3)          =>  throws ImIndexOutOfBoundsException
     *     
     * Unlike standard Java lists this is not a constant time operation. It is linear
     * in its argument.
     * 
     * @throws NoSuchElementException if `indexStartingAtOne > size()` or `indexStartingAtOne < 1`
     * @see #get(int)
     */
    public T get1(int indexStartingAtOne)
    {
        ImIndexOutOfBoundsException.check(indexStartingAtOne, size(), "indexStartingAtOne");

        ImList<T> node = this;

        for (int i = 1; i < indexStartingAtOne; i++)
        {
            node = node.tail();
        }

        return node.head();
    }

    /**
     * The element at `indexStartingAtZero`.
     * 
     * This method just does this:
     * 
     *      return at(indexStartingZero + 1);   
     * 
     * @throws NoSuchElementException if `indexStartingAtZero >= size()` or `indexStartingAtOne < 0`
     * @see #get1(int)
     */
    public T get(int indexStartingAtZero)
    {
        ImIndexOutOfBoundsException.check0(indexStartingAtZero, size(), "indexStartingAtZero");

        return get1(indexStartingAtZero + 1);
    }

    /**
     * The list whose elements are the same as the first `numberToTake` elements
     * of `this`. If
     * 
     *     numberToTake >= this.size()
     *     
     * then return `this`.
     * 
     * ### Examples:
     * 
     *     ImList.on(1, 2, 3, 4).take(2) =>  [1, 2]
     *     ImList.on(7).take(77)         =>  [7]
     *     ImList.on().take(3)           =>  []
     */
    @SuppressWarnings("unchecked")
    public ImList<T> take(int numberToTake)
    {
        return ImList.joinArray(asList(Math.max(0, numberToTake)), ImList.<T> empty());
    }

    /**
     * The list whose elements are the last `size - numberToDrop` elements of `this`.
     * 
     * If `numberToDrop >= this.size()`
     * the list is obtained by invoking `tail()` `numberToDrop` times
     * else it is the empty list.
     * 
     * ### Examples:
     * 
     *     ImList.on(1, 2, 3, 4).drop(2)  =>  [3, 4]
     *     ImList.on(7).drop(77)          =>  []
     *     ImList.on().drop(3)            =>  []
     */
    public ImList<T> drop(int numberToDrop)
    {
        ImList<T> result = this;

        for (int i = 0; i < numberToDrop; i++)
        {
            if (result.isEmpty())
            {
                return result;
            }
            result = result.tail();
        }

        return result;
    }

    /**
     * A string representation of this list.
     * 
     * The string
     * representation consists of a list of the collection's elements in the
     * order they are returned by its iterator, enclosed in square brackets
     * (<tt>"[]"</tt>).Adjacent elements are separated by the characters
     * <tt>", "</tt> (comma and space).
     * 
     * Elements are converted to strings as
     * by {@link String#valueOf(Object)}.
     * 
     * ### Examples:
     * 
     *     on()         =>  "[]"
     *     on(1, 2, 3)  =>  "[1, 2, 3]"
     *
     */
    @Override
    public String toString()
    {
        return "[" + TextUtils.join(iterator(), ", ") + "]";
    }

    /**
     * `true` if `this` contains `elementToLookFor`, `false` otherwise.
     * 
     * More formally, returns `true` if and only if `this` contains
     * at least one element `e` such that
     * 
     *     e.equals(elementToLookFor)
     *
     * ### Examples:
     * 
     *     on(1, 2, 1).contains(1)     =>  true
     *     on(1, 2, 1).contains(null)  =>  throws java.lang.NullPointerException: ImCollections can't contain nulls
     */
    @Override
    public boolean contains(Object elementToLookFor)
    {
        return indexOf(elementToLookFor) != -1;
    }

    /**
     * Returns the index (starting at one) of the first occurrence of `elementToLookFor`,
     * or -1 if no such element exists.
     * 
     * More formally, returns the lowest index `i` such that
     * 
     *     at(i).equals(elementToLookFor)
     *     
     * or `-1` if there is no such index.
     * 
     *     on(1, 2, 3).indexOf(1)      =>  1
     *     on(1, 2, 3).indexOf(1.0)    =>  -1
     *     on().contains(null)  =>  throws java.lang.NullPointerException: ImCollections can't contain nulls
     */
    public int indexOf(Object elementToLookFor)
    {
        NullCheck.checkThrowingNPE(elementToLookFor);

        int index = 0;
        for (T thing : this)
        {
            index++;
            if (thing.equals(elementToLookFor))
                return index;
        }

        return -1;
    }

    /**
     * The hash code value for `this`.
     *
     * Because ImLists are immutable, the hash code is calculated only once when the list is
     * created and cached.
     * 
     * This implementation uses a similar algorithm that used to define the
     * list hash function in the documentation for the {@link List#hashCode}
     * method - except that the order of the elements is reversed.
     * 
     * This allows us to calculate the hash code efficiently at list creation time based on the
     * hash code of the head
     * element and the hash code of the tail list.
     *
     */
    public int hashCode()
    {
        return hashCode;
    }

    /**
     * An `ArrayList` whose elements are the same as `this` and whose size is
     * 
     *     min(numberToTake, size())
     */
    private List<T> asList(int numberToTake)
    {
        int n = Math.min(numberToTake, size());
        ArrayList<T> result = new ArrayList<T>(n);

        ImList<T> node = this;
        for (int i = 0; i < n; i++)
        {
            result.add(node.head());
            node = node.tail();
        }

        return result;
    }

    /**
     * The list whose elements are those of `this` with `sep` inserted between each element
     * pair.
     * 
     * ImCollections can't contain null so `sep` must not be `null`.
     * 
     * ### Examples:
     * 
     *     onArray(1, 2, 3, 5).intersperse(0)  =>  [1, 0, 2, 0, 3, 0, 5] 
     *     onArray(1).intersperse(0)           =>  [1]
     *     onArray().intersperse(0)            =>  []
     *     onArray(1).intersperse(null)        =>  throws java.lang.NullPointerException: ImCollections can't contain nulls
     *     onArray().intersperse(null)         =>  throws java.lang.NullPointerException: ImCollections can't contain nulls
     *    
     * @throws NullPointerException
     */
    public ImList<T> intersperse(T sep)
    {
        NullCheck.check(sep);
        ImList<T> result = ImList.empty();
        List<T> old = (List<T>) this.asList(size());

        for (int i = old.size() - 1; i >= 0; i--)
        {
            result = ImList.cons(old.get(i), result);

            if (i > 0)
                result = ImList.cons(sep, result);
        }

        return result;
    }

    /**
     * The list whose elements are the same as in `this` but where the order is reversed.
     * 
     * For all lists, `l`:
     * 
     *     l.reversed().reversed().equals(l)
     * 
     * ### Examples:
     * 
     *     ImList.on(1, 2, 3).reversed()  =>  [3, 2, 1]
     *     ImList.on().reversed()         =>  []
     * 
     */
    public ImList<T> reversed()
    {
        ImList<T> node = ImList.<T> empty();

        ImList<T> old = this;

        while (old != ImList.empty())
        {
            node = new ImList<T>(old.head(), node);
            old = old.tail();
        }

        return node;
    }

    /**
     * The list where the i-th element is the result of evaluating the single argument function `fn` on
     * the i-th element of `this`.
     * 
     * ### Examples:
     * 
     * To convert a list of objects to a list of their string representations:
     * 
     *     Function1<String> toStringFn = FnFactory.on(Object.class).getFn(String.class, "toString");
     *     ImList.onArray(1, 2).map(toStringFn)  => "[1, 2]"
     *         
     * To parse a list of strings to their Integer equivalents: 
     *     
     *     Function1<Integer> parseIntFn = FnFactory.on(Integer.class).getFnStatic(int.class, "parseInt", String.class);        
     *     ImList.onArray("1", "2").map(parseIntFn)  =>  "[1, 2]"       
     *             
     * To parse with a radix of 16, we first get the parse function with two arguments, then we create a new function        
     * out of this with the arguments reversed. Then, if we supply the radix argument of 16 to this function,        
     * we will have a new function of one argument that does what we want:
     *       
     *     Function2<Integer> parseIntWithRadixFn = FnFactory.on(Integer.class).getFnStatic( //        
     *             int.class, "parseInt", String.class, int.class);        
     *             
     *     Function1<Integer> parseHexFn = parseIntWithRadixFn.flip().invoke(16);        
     *     ImList.onArray("8", "D", "15").map(parseHexFn)  =>  [8, 13, 21]       
     *     
     * @see immutablecollections.functions
     * @see #fold
     */
    public <O> ImList<O> map(Function1<O> fn)
    {
        @SuppressWarnings("unchecked")
        ImList<O> result = (ImList<O>) ImList.empty();

        for (T e : this)
        {
            result = new ImList<O>(fn.invoke(e), result);
        }

        return result.reversed();
    }

    /**
     * The list with head `head` and tail `tail`.
     * 
     * ImCollections can't contain null so `head` must not be `null`.
     * 
     * Examples:
     * 
     *     cons(1, onArray(2, 3))  =>  [1, 2, 3] 
     *     cons(1, onArray())      =>  [1]
     *     cons(null, on(1))       =>  throws java.lang.NullPointerException: ImCollections can't contain nulls
     *    
     *  @throws NullPointerException
     */
    public static <T> ImList<T> cons(T head, ImList<? extends T> tail)
    {
        return new ImList<T>(head, tail.<T> upCast());
    }

    /**
     * The list of all lists that are *subsequences* of this.
     *
     * To say that the list `sub` is a *subsequence* of the list `whole` means that
     * `sub` can be obtained from `whole` by removing zero or more elements (but not reordering
     * any elements).
     * 
     * This definition means that any list is a *subsequences* of itself and the empty list is
     * a *subsequence* of all lists.
     * 
     * ### Examples:
     * 
     *     powerSet(empty())      =>  [[]]
     *     powerSet(on(1))        =>  [[1], []]
     *     powerSet(on(1, 2))     =>  [[1, 2], [1], [2], []]
     *     powerSet(on(1, 2, 3))  =>  [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

     */
    @SuppressWarnings({ "unchecked", "rawtypes" })
    public ImList<ImList<T>> powerSet()
    {
        if (isEmpty())
        {
            return on(ImList.<T> empty());
        }
        else
        {
            // We tried using the 'proper type' here like this:
            // ImList<ImList<T>> psTail = tail().powerSet();
            // but the compiler says "no" for the return line:
            //
            // Type mismatch: cannot convert from ImList<ImList<? extends Object>> to ImList<ImList<T>>
            // because we have consFn declared statically
            // so we will just use raw types instead

            ImList powerSetOfTail = tail().powerSet();

            // Here we are using the `cons` function that has been defined earlier
            return ImList.joinArray(powerSetOfTail.map(consFn.invoke(head())), powerSetOfTail);
        }
    }

    private Object readResolve() throws ObjectStreamException
    {
        return size == 0
                ? empty
                : this;
    }

    /**
     * The (singleton) empty list.
     * 
     * The following expressions evaluate to `true`:
     * 
     *    onArray().equals(ImList.empty())
     *    onArray() == ImList.empty()
     *    ImList.on(1).tail() == ImList.<Integer> empty(), 
     * 
     * To use it you will sometimes need to give the Java compiler a hint about what type
     * of list you want. In order to do this you will have to fully qualify the method invocations.
     * 
     * Examples:
     * 
     *     // Ok
     *     ImList<Integer> ints2;
     *     if (condition)
     *         ints2 = ImList.empty();
     *     else
     *         ints2 = ImList.on(1);
     * 
     *     // Needs hint
     *     ImList<Integer> ints = condition
     *             ? ImList.<Integer> empty()
     *             : ImList.on(1);
     * 
     *     // Ok
     *     ImList<? extends String> es = ImList.empty();
     * 
     *     // Needs hint
     *     ImList<String> c = ImList.cons("c", ImList.<String> empty());
     * 
     *     // Ok
     *     boolean b1 = onArray() == ImList.empty();
     * 
     *     // Needs a hint
     *     boolean b2 = on(1).tail() != ImList.<Integer> empty();
     */
    @SuppressWarnings("unchecked")
    public static <T> ImList<T> empty()
    {
        return (ImList<T>) empty;
    }

    /**
     * The list whose elements are obtained from `array`.
     * 
     * ImCollections can't contain `null` so none of the elements in `array` can be `null`
     * 
     * ### Examples:
     * 
     *     onArray(1, 2, 3)                      => [1, 2, 3]
     *     onArray(new Integer[] { 1, 2, 3 })    => [1, 2, 3]
     *     onArray()                             => []
     *     onArray(null, 2, 3)                   => throws java.lang.NullPointerException: ImCollections can't contain nulls
     * 
     * @throws NullPointerException if any of the elements in `array` is `null`
     * @see #onAll(Collection)
     * @see #onIterator(Iterator)
     * @see #on
     */
    public static <A> ImList<A> onArray(A... array)
    {
        ImList<A> list = empty();

        for (int i = array.length - 1; i >= 0; i--)
        {
            list = list.cons(array[i]);
        }

        return list;
    }

    /**
     * The list whose elements are obtained from `elementsCollection`.
     * 
     * ImCollections can't contain `null` so none of the elements in `elementsCollection` can be `null`
     * 
     * ### Examples:
     * 
     *     onAll(Arrays.asList(1, 2, 3))    => [1, 2, 3]
     *     onAll(Arrays.asList())           => []
     *     onAll(Arrays.asList(1, null, 3)) => throws java.lang.NullPointerException: ImCollections can't contain nulls
     * 
     * @throws NullPointerException if any of the elements in `elementsCollection` is `null`
     * @see #onIterator(Iterator)
     * @see #onArray(Object...)
     * @see #on
     */
    @SuppressWarnings("unchecked")
    public static <A> ImList<A> onAll(Collection<? extends A> elementsCollection)
    {
        return elementsCollection instanceof ImList
                ? (ImList<A>) elementsCollection
                : elementsCollection instanceof ArrayList
                        ? onArrayList((ArrayList<A>) elementsCollection, ImList.<A> empty())
                        : onIterator(elementsCollection.iterator());
    }

    /**
     * The list whose elements are obtained by iterating over `iterator`.
     * 
     * ImCollections can't contain `null` so none of the elements in `iterator` can be `null`
     * 
     * ### Examples:
     * 
     *     onIterator(Arrays.asList(1, 2, 3).iterator())    => [1, 2, 3]
     *     onIterator(Arrays.asList().iterator())           => []
     *     onIterator(Arrays.asList(1, null, 3).iterator()) => throws java.lang.NullPointerException: ImCollections can't contain nulls
     * 
     * @throws NullPointerException if any of the elements in `iterator` is `null`
     * @see #onAll(Collection)
     * @see #onArray(Object...)
     * @see #on
     */
    public static <A> ImList<A> onIterator(Iterator<? extends A> iterator)
    {
        ArrayList<A> elements = new ArrayList<A>();

        while (iterator.hasNext())
        {
            elements.add(iterator.next());
        }

        return onArrayList(elements, ImList.<A> empty());
    }

    private static <A> ImList<A> onArrayList(ArrayList<A> elements, ImList<A> tail)
    {
        ImList<A> list = tail;
        for (int i = elements.size(); i >= 1; i--)
        {
            list = new ImList<A>(elements.get(i - 1), list);
        }

        return list;
    }

    /**
     * The list whose only element is `element`.
     * 
     * This is convenient when we want to create a list whose only element is an array. If we tried to use {@link #onArray(Object...)}
     * with a single argument that was an array it would generate a list containing the elements in the array
     * instead of a list containing one element that is an array.
     * 
     * ImCollections can't contain `null` so `element` can't be `null`.
     * 
     * ### Examples
     * 
     *     on(1)     => [1]
     *     on(null)  => throws java.lang.NullPointerException: ImCollections can't contain nulls
     *     
     *     Integer[] ints = new Integer[] { 1, 2, 3 };
     *     
     *     on(ints).size()                       =>  1
     *     on(ints).head().getClass().isArray()  =>  true
     * 
     * @throws NullPointerException
     * @see #onArray(Object...)
     * @see #onIterator(Iterator)
     * @see #onArray(Object[])
     */
    public static <A> ImList<A> on(A element)
    {
        return new ImList<A>(element, ImList.<A> empty());
    }

    /**
     * Allows `ImList<U>` to be cast to `ImList<T>` (where U is a subtype of T) without generating a compiler warning.
     * 
     * Of course Java does not regard this cast as type safe because of the "cuckoo in the nest" problem:
     * 
     *     List<String> strings = new ArrayList<String>();
     *     List<Object> nest = strings; // Java does not allow this
     *     // strings and nest now refer to the same list
     *     Object cuckoo = new Object();
     *     nest.add(cuckoo);
     *     strings.get(0).length();
     *     // java.lang.ClassCastException: java.lang.Object cannot be cast to java.lang.String
     *     
     * But since ImCollections are *immutable* it is always safe to cast them in this way.
     * 
     * Having established that it is safe to cast in this way, the problem is that it is surprisingly difficult
     * to actually do it without the Java compiler getting very cross.
     * 
     * Assuming `ints` and `numbers` declared like this:
     * 
     *     ImList<Integer> ints ...
     *     ImList<Number> numbers ...
     * 
     * let's see what the Java compiler has to say
     * when we naively try various approaches (These error/warnings are from the Eclipse Java compiler):
     * 
     * This obviously produces an error:
     * 
     *     numbers = ints; => Type mismatch: cannot convert from ImList<Integer> to ImList<Number> 
     *
     * This also produces an error:
     * 
     *     numbers = (ImList<Number>) ints; => Cannot cast from ImList<Integer> to ImList<Number> 
     *
     * In desperation (how many times have we all been here?) we try this:
     * 
     *     numbers = (ImList<? extends Number>) ints;
     *     => Type mismatch: cannot convert from ImList<capture#1-of ? extends Number> to ImList<Number>   
     *
     * This somewhat recondite cast *is* allowed, merely generating a warning:
     * 
     *     numbers = (ImList<Number>) (ImList<? extends Number>) ints;
     *     => Type safety: Unchecked cast from ImList<capture#1-of ? extends Number> to ImList<Number>
     * 
     * Using upCast:
     * 
     *     numbers = ints.<Number>upCast();
     *     
     * In fact, in this particular case it is even simpler:
     * 
     *     numbers = ints.upCast();
     *     
     * Strictly, the {@link #onAll(Collection)} method can achieve the same effect:
     * 
     *     numbers = ImList.<Number> onAll(ints);
     * 
     * but the instance method `upCast()` feels clearer to us and, in some case does not need any qualification.
     *
     * @see #empty()
     */
    @SuppressWarnings("unchecked")
    public <U> ImList<U> upCast()
    {
        return (ImList<U>) this;
    }

    /**
     * The ImList formed out of the elements of each collection in `collections` in order.
     * 
     * ImCollections can't contain `null` so none of the elements can be `null`
     * 
     * ### Examples:
     * 
     *     List<Number> threeFive = Arrays.<Number> asList(3, 5);
     *     ImList<Integer> oneTwo = ImList.onArray(1, 2);
     *     
     *     joinArray(oneTwo, threeFive)          =>  [1, 2, 3, 5]
     *     joinArray(oneTwo, threeFive, oneTwo)  =>  [1, 2, 3, 5, 1, 2]
     *     joinArray(onArray(), onArray())       =>  []
     * 
     * @see #addingAll(Collection)
     * @see #joinIterator(Iterator)
     * @see #join(Collection)
     */
    public static <A> ImList<A> joinArray(Collection<? extends A>... collections)
    {
        return joinIterator(ArrayIterator.on(collections));
    }

    /**
     * The ImList formed out of the elements of each collection in `iterator` in order.
     * 
     * ImCollections can't contain `null` so none of the elements can be `null`
     * 
     * @see #addingAll(Collection)
     * @see #joinArray(Collection...)
     * @see #join(Collection)
     */
    public static <A> ImList<A> joinIterator(Iterator<Collection<? extends A>> iterator)
    {

        ArrayList<A> elements = new ArrayList<A>();

        while (iterator.hasNext())
            elements.addAll(iterator.next());

        return onArrayList(elements, ImList.<A> empty());
    }

    /**
     * The ImList formed out of the elements of each collection in `collectionOfCollections` in order.
     * 
     * ImCollections can't contain `null` so none of the elements can be `null`
     * 
     * @see #addingAll(Collection)
     * @see #joinArray(Collection...)
     * @see #joinIterator(Iterator)
     */
    public static <A> ImList<A> join(Collection<? extends Collection<? extends A>> collectionOfCollections)
    {
        return joinIterator((Iterator<Collection<? extends A>>) collectionOfCollections.iterator());
    }

    /**
     * The ImList formed out of the elements of `this` followed by the elements in `other` in order.
     * 
     * ImCollections can't contain `null` so none of the elements can be `null`
     * 
     * @see #join(Collection)
     * @see #joinArray(Collection...)
     * @see #joinIterator(Iterator)
     */
    public ImList<T> addingAll(Collection<? extends T> other)
    {
        return onArrayList(new ArrayList<T>(this), ImList.onAll(other));
    }

    /**
     * Compares `another` with `this` for equality.  Returns
     * `true` if and only if the specified object is also an `ImList`, both
     * lists have the same size, and all corresponding pairs of elements in
     * the two lists are *equal*.
     * 
     *  `e1` and `e2` being *equal* means
     * 
     *     e1.equals(e2) == true
     * 
     * In other words, two ImLists are defined to be
     * equal if they contain *equal* elements in the same order.
     * 
     * In *other* other words - this is very similar to the standard Java List `equals`.
     *
     */
    @SuppressWarnings("rawtypes")
    @Override
    public boolean equals(Object other)
    {
        return this == other
                ? true
                : other instanceof ImList
                        ? eq((ImList) other)
                        : false;
    }

    private boolean eq(ImList<?> otherList)
    {
        return size() == otherList.size() && hashCode() == otherList.hashCode()
                ? elementsEq(iterator(), otherList.iterator())
                : false;
    }

    private boolean elementsEq(Iterator<?> itOne, Iterator<?> itTwo)
    {
        while (itOne.hasNext())
        {
            if (!itOne.next().equals(itTwo.next()))
                return false;
        }
        return true;
    }

    public ImListZipper<T> getZipper()
    {
        return ImListZipper.on(this);
    }

    public ImList<T> cons(T head)
    {
        return ImList.cons(head, this);
    }

    public String toString(Function1<String> fn)
    {
        return "[" + TextUtils.join(map(fn).iterator(), ", ") + "]";
    }

}
